package b2_heap;

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * 基于整型的最大堆实现
 */
public class MaxHeap {
    //使用动态数组存储最大堆
    private List<Integer> data;

    //构造方法
    public MaxHeap() {
        this(10);
    }
    public MaxHeap(int size) {
        this.data = new ArrayList<>(size);
    }
    //数组堆化,O(N)
    public MaxHeap(int[] arr) {
        this.data = new ArrayList<>(arr.length);
        //将元素放入data中
        for(int i : arr){
            data.add(i);
        }
        //从最后一个非叶子节点开始倒着下沉每一个节点，直到堆顶
        for(int i = parent(data.size()-1); i >= 0; i--){
            siftDown(i);
        }
    }

    //添加元素
    public void add(int val) {
        // 1.先将元素添加到数组末尾
        data.add(val);
        // 2.进行元素的上浮操作
        siftUp(data.size() - 1);
    }
    /** 元素上浮操作 **/
    private void siftUp(int k) {
        //确认终止条件，当到达顶部时不需要继续上浮
        //并且只有该节点值>父节点时，才进行上浮
        while(k > 0 && data.get(k) > data.get(parent(k))){
            //交换该节点和父节点的val值
            swap(k, parent(k));
            //更新索引为父节点的索引
            k = parent(k);
        }
    }
    //交换两个索引处的val值
    private void swap(int i, int j) {
        int temp = data.get(i);
        data.set(i, data.get(j));
        data.set(j, temp);
    }

    //弹出最大堆的最大值
    public int extractMax() {
        //判断堆是否为空
        if(isEmpty()){
            throw new NoSuchElementException("Heap is empty! Cannot extract!");
        }
        int maxVal = data.get(0);
        // 1.将末尾元素顶到堆顶
        int lastVal = data.get(data.size() - 1);
        data.set(0, lastVal);
        // 2.将末尾元素删除
        data.remove(data.size() - 1);
        // 3.进行元素下沉操作
        siftDown(0);
        return maxVal;
    }
    /** 元素下沉操作 **/
    private void siftDown(int k) {
        //原理：该节点和它的左右孩子比较，如果该节点值<孩子的值，则swap(cur.val, max(left.val,right.val));
        //并且继续向下比较，再让刚刚交换过的孩子节点和它的孩子作比较，直到叶子节点
        while(leftChild(k) < data.size()){
            //此时，说明存在左孩子
            int leftRightMaxIndex = leftChild(k);
            if(rightChild(k) < data.size()){
                //说明也存在右孩子,比较两个孩子的大小
                if(data.get(rightChild(k)) > data.get(leftChild(k))){
                    leftRightMaxIndex = rightChild(k);
                }
            }
            if(data.get(k) >= data.get(leftRightMaxIndex)){
                //当前节点值>=孩子值，结束循环
                break;
            }else{
                swap(k, leftRightMaxIndex);
                k = leftRightMaxIndex;
            }
        }
    }

    //返回堆顶元素：最大值
    public int peekMax() {
        if(isEmpty()){
            throw new NoSuchElementException("Heap is empty! Cannot peek!");
        }
        return data.get(0);
    }

    //判断堆是否为空
    public boolean isEmpty() {
        return data.size() == 0;
    }

    public String toString() {
        return data.toString();
    }

    //根据当前节点索引得到父节点的索引
    private int parent(int k) {
        return (k-1) / 2;
    }
    //根据当前节点索引得到左孩子的索引
    private int leftChild(int k) {
        return (2*k) + 1;
    }
    //根据当前节点索引得到右孩子的索引
    private int rightChild(int k) {
        return (2*k) + 2;
    }
}
